package com.chenxys.algorithm.newbie;

/**
 * <p>
 *      使用位运算实现 + - * / <br/>
 *      <a href="https://leetcode.com/problems/divide-two-integers">测试题</a>
 * </p>
 *
 * @author Chenxys
 * @version V1.0
 * @Package com.chenxys.algorithm.newbie
 * @date 12/31/23 3:11 PM
 * @Copyright ©
 */
public class BitAddMinusMultiDiv {

    /**
     * <p>
     *     使用位运算实现两数相加
     * </p>
     * @param a 整数a
     * @param b 整数b
     * @return a+b
     */
    public static int add(int a, int b){
        // a + b ==> (a ^ b) + 进位
        int sum = a;
        // 进位为空时，即为答案
        while (b != 0){
            // ^ --> 无进位相加
            sum = a ^ b;
            // a & b --> 进位信息
            // 哪里进位了,前一位 即 (a & b) << 1
            b = (a & b) << 1;
            // 将当前无进位结果重新赋值给a
            a = sum;
        }
        return sum;
    }

    /**
     * <p>
     *     对一个数取反 -- > n的相反数 ==> ~n + 1
     * </p>
     * @param n 待取反数
     * @return 取反后的数
     */
    public static int negNum(int n){
        return add(~n, 1);
    }

    /**
     * <p>
     *     a - b ==> a + b的相反数
     * </p>
     * @param a 被减数
     * @param b 减数
     * @return 差
     */
    public static int minus(int a, int b){
        return add(a, negNum(b));
    }

    /**
     * <p>
     *     乘法<br/>
     *     <img src="/Users/chenxys/code/algorithm/src/main/resources/imgs/newbie-multi.png"/>
     * </p>
     * @param a 乘数
     * @param b 被乘数
     * @return 积
     */
    public static int multi(int a, int b){
        int res = 0;
        // 类似乘法计算的方式只不过把整数换成二进制
        while (b != 0) {
            // 如果乘数不为0,则直接加被乘数
            if ((b & 1) != 0) {
                res = add(res, a);
            }
            // 被乘数左移一位
            a <<= 1;
            //乘数右移一位
            b >>>= 1;
        }
        return res;
    }

    /**
     * <p>
     *     判断一个数是否为负数
     * </p>
     * @param n 待判断数
     * @return 是否为负数
     */
    public static boolean isNeg(int n){
        return n < 0;
    }

    /**
     * <p>
     *     除法 x/y
     * </p>
     * @param a 被除数
     * @param b 除数
     * @return 商
     */
    public static int div(int a, int b){
        // 取正整数,若不取正整数,则在右移过程中可能将符号位也右移
        int x = isNeg(a) ? negNum(a) : a;
        int y = isNeg(b) ? negNum(b) : b;
        // 结果
        int res = 0;
        // int类型二进制除去符号位共31位 ,从除符号位之外的最高位开始比较
        // 所以i = 30,递减
        for (int i = 30; i >= 0; i = minus(i, 1)) {
            // 右移不涉及修改符号位
            // 如果被除数右移i位，比除数大[让除数和自己最高位最接近]
            if ((x >> i) >= y){
                // 那么证明第i位为1,将第i位设置为1
                res |= (1 << i);
                // 将被除数 - (除数 << i) 再次计算得到被除数
                x = minus(x, y << i);
            }
        }
        // 返回结果[如果a,b符号不一样,取负号返回;符号一样,直接返回]
        return isNeg(a) ^ isNeg(b) ? negNum(res) : res;
    }

    /**
     * <p>
     *     a/b
     * </p>
     * @param a 被除数
     * @param b 除数
     * @return 商
     */
    public static int divide(int a, int b){
        // 如果 a,b 均为系统最小值,则直接返回1
        if (a == Integer.MIN_VALUE && b == Integer.MIN_VALUE) {
            return 1;
        } else if (b == Integer.MIN_VALUE) {
            // 除数为系统最小值,则直接返回0
            return 0;
        } else if (a == Integer.MIN_VALUE) {
            // 被除数为系统最小值
            // 除数为 - 1
            if (b == negNum(1)) {
                // 直接返回系统最大[LeetCode约定]
                return Integer.MAX_VALUE;
            } else {
                // a / b
                // (a + 1) / b == c
                // a - (b * c ) = d
                // d / b = e;
                // return c + e
                int c = div(add(a, 1), b);
                return add(c, div(minus(a, multi(c, b)), b));
            }
        } else {
            // a,b均不是系统最小值
            return div(a, b);
        }


        /*if (a == Integer.MAX_VALUE && b == Integer.MAX_VALUE) {
            return 1;
        } else if (b == Integer.MAX_VALUE) {
            return 0;
        } else if (a == Integer.MAX_VALUE) {
            if (b == negNum(1)) {
                return Integer.MAX_VALUE;
            } else {
                int c = div(add(a, 1), b);
                return add(c, div(minus(a, multi(c, b)), b));
            }
        } else {
            return div(a, b);
        }*/
    }

}
